package com.example.demo.zaqizabatest.sort;

import java.util.Arrays;

/**
 * @ClassName MergeSort
 * @Author lys4134
 * @Date 2022/03/04 16:20:36
 * @Description MergeSort
 * @Version 1.0
 **/
public class MergeSort {

    public static void main(String[] args) {
        int[] nums = new int[]{3, 2, 6, 9, 8, 10, 1};
        sort(nums, 0, nums.length - 1);
        System.out.println(Arrays.toString(nums));
    }

    /**
     * 将数组拆分成多个数组，最小数组只有一个值
     *
     * @param nums
     */
    public static void sort(int[] nums, int left, int right) {
        // 当只剩下一个元素时不再拆分
        if (left == right) {
            return;
        }
        int mid = (left + right) / 2;
        // 左边拆分
        sort(nums, left, mid);
        // 右边拆分
        sort(nums, mid + 1, right);
        // 合并
        merge(nums, left, right, mid);
    }

    /**
     * 将数组left,mid以及数组mid+1,right合并
     *
     * @param nums
     * @param left
     * @param right
     * @param mid
     */
    public static void merge(int[] nums, int left, int right, int mid) {
        if (left == right) {
            return;
        }
        int length = right - left + 1;
        // 建立一个临时数组存两个数组
        int[] temp = new int[length];
        int index1 = left, index2 = mid + 1, index = 0;
        // 两个数组逐步遍历，谁小谁先进，直至一个完毕
        while (index1 <= mid && index2 <= right) {
            temp[index++] = nums[index1] < nums[index2] ? nums[index1++] : nums[index2++];
        }
        // 剩余数组最后应该入temp数组的原数组下标
        int i = index1 > mid ? index2 : index1;
        // 只要temp数组未满，就一直加入，因为temp数组是两个数组长度之和，所以不会超界
        while (length > index) {
            temp[index++] = nums[i++];
        }
        // 将临时数组数据全部拷入nums数组中
        System.arraycopy(temp, 0, nums, left, length);
    }


    /**
     * 交换位置
     *
     * @param nums
     * @param i
     * @param j
     */
    public static void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}
